This invention relates to a method of setting up a temporary local area network (also referred to as a xe2x80x9cLANxe2x80x9d) generally set up solely of terminals and not having a fixed backbone network, a method of communicating using this network, and a terminal for use in the network.
Known examples of LAN configurations include a LAN connected to a fixed backbone network via a router of the kind described in document (1) xe2x80x9cInterconnections: Bridges and Routersxe2x80x9d by Radia Perlman, Addison-Wesley, 1992 (this LAN is referred to as a xe2x80x9cbackbone-connected LANxe2x80x9d), and a LAN temporarily set up solely of terminals and not connected to a backbone network via a router, as described in document (2) xe2x80x9cRouting in Ad Hoc Networks of Mobile Hostsxe2x80x9d by David B. Johnson, Proceedings of the Workshop on Mobile Computing Systems and Applications, pp. 158xcx9c163, IEEE Computer Society, Santa Cruz, Calif., December 1994 (this LAN is referred to as an xe2x80x9cad hoc LANxe2x80x9d).
These LANs have different features and the circumstances in which they are used differ in the following way: In the case of the backbone-connected LAN, communication is carried out among terminals and servers connected to other LANs mutually connected by a fixed backbone network. A backbone-connected LAN is suited to a regularly performed operation such as the sending and receiving of electronic mail for a daily business.
An ad hoc LAN, on the other hand, brings together terminals having a communication function and only these terminals communicate with one another. This LAN is useful in a scenario such as a conference in which the participants gather together bringing their terminals with them.
The configurations of a backbone-connected LAN and ad hoc LAN are illustrated in FIGS. 8 and 9, respectively.
As shown in FIG. 8, backbone-connected LANs 1010, 1020 are connected to a backbone network 1000. Though only two backbone-connected LANs are depicted in FIG. 8, there are instances where three or more of these LANs are thus connected.
The internal construction of the backbone-connected LANs will be described taking the LAN 1010 as an example.
As shown in FIG. 8, the backbone-connected LAN 1010 is connected to the backbone network 1000 via a router 1005. Conceivable transmission media are a physical wire as at 1007 or a wireless link as at 1006. Examples of terminals used within the backbone-connected LAN are a wired terminal 1004 connected via the wire transmission medium 1007 and wireless terminals 1001, 1002 connected via the wireless transmission medium 1006. The wireless terminals 1001, 1002 are capable of communicating with the wired terminal 1004 and router 1005, which are connected to the wired medium 1007, via a wireless base station 1003.
Further, the terminals in the backbone-connected LAN 1010 communicate with terminals connected to another backbone-connected LAN, such as the backbone-connected LAN 1020, via the router 1005 and backbone network 1000.
The ad hoc LAN, on the other hand, is constructed as shown in FIG. 9. FIG. 9 schematically illustrates the manner in which two ad hoc LANs 1100 and 1110 exist. Though only two ad hoc LANs are depicted in FIG. 9, there are instances where three or more of these LANs may exist.
As shown in FIG. 9, the ad hoc LANs 1100 and 1110 include three wireless terminals 1101, 1102, 1103 and 1111, 1112, 1113, respectively. The wireless terminals within each ad hoc LAN communicate with one another via wireless transmission media 1104 and 1114, respectively, but there is no communication between the ad hoc LANs. Though FIG. 9 illustrates an arrangement in which the ad hoc LANs use wireless transmission media, it is possible to adopt an arrangement in which only wired transmission media are used or one in which both wired and wireless transmission media are employed.
A method relying upon connection by a router and a method relying upon connection by a bridge are known as methods of connecting different LANs. For example, see the document (1) above (xe2x80x9cInterconnections: Bridges and Routersxe2x80x9d by Radia Perlman, Addison-Wesley, 1992).
Such arrangements are illustrated in FIGS. 10 and 11, which show the manner in which a terminal A (1121) and a terminal B (1131) communicate with each other in a case where different LANs comprising respective transmission media 1120, 1130 are interconnected via a relay node 1125 (FIG. 10) or 1126 (FIG. 11).
FIG. 10 illustrates connection by router, in which the relay node 1125 functions as the router. In this case the relay node 1125 is such that processing for transferring packets used in communication between the terminal A and the terminal B is executed in the network layer.
FIG. 11, on the other hand, illustrates connection by bridge, in which the relay node 1126 functions as the bridge. In this case the relay node 1126 is such that processing for transferring packets used in communication between the terminal A and the terminal B is executed in the data link layer.
The router arrangement is implemented using addresses in the network layer. Though transfer processing presents a heavy load, flexible control is possible.
With the bridge arrangement, on the other hand, only simple transfer control can be carried out but the transfer processing is simple.
Multicast communication is known as a communication scheme in which bandwidth is utilized effectively. According to multicast communication, a plurality of parties are defined as a group, and in case of communication within the group, data is not transmitted to the individual parties but is instead multicast to the defined group by a single transmission. For a description of multicasting, see document (3) xe2x80x9cMbone: Interactive Multimedia on the Internetxe2x80x9d by Vinay Kimar, New Riders Publishing, 1995 etc.
Multicasting is implemented by defining a multicast address for each multicast group. In a case where data is transmitted to a certain multicast group, the data is transmitted with the multicast address of this group serving as the destination address. A terminal participating in the multicast group receives the data that has been transmitted using the multicast address of the group as the destination of the transmission. The packet format used in such multicast communication is as shown in FIG. 14. As shown in FIG. 14, the format includes a network layer header 1300 and higher layer data 1301. The network layer header 1300 includes a multicast address as the destination and a transmitting terminal address as the address of the transmitting party.
In the course toward the prevent invention, the following problems have been encountered.
From the user standpoint, it would be desirable to be able to simultaneously perform, through use of a single terminal, daily communication such as email communication using a backbone-connected LAN and temporary communication provided by an ad hoc LAN. However, a backbone-connected LAN and an ad hoc LAN are separate, independent entities and one terminal cannot be connected to both LANs at the same time. This means that two different terminals are required in a case where the user wishes to communicate with both a backbone-connected LAN and an ad hoc LAN.
Conventional methods of connecting two different LANs include the bridge connection and the router connection, as illustrated in FIGS. 10 and 11.
If a terminal possesses a function for implementing a connection between LANs, it is possible for the terminal to be connected to both a backbone-connected LAN and an ad hoc LAN. However, most terminals have a construction of the kind shown in FIG. 12.
As illustrated in FIG. 12, network layer software 211 performs an exchange of data with a device driver 1200, which is dependent upon a transmitter/receiver 1201 that executes the processing of a data link layer and physical layer, via a standard interface (interface 1 in FIG. 12) such as one in accordance with the NDIS (Network Driver Interface Standard).
Thus, the usual terminal has a construction different from that of the relay nodes 1125, 1126 in FIGS. 10 and 11.
In order for a terminal to be provided with a function (a router function) similar to that of the relay node 1125 (see FIG. 10), it is required that the network layer software 211 be modified. In order for a terminal to be provided with a function (a bridge function) similar to that of the relay node 1126 (see FIG. 11), it is required that the transmitter/receiver 1201 or device driver 1200 be modified. Consequently, the modification costs entailed to enable a terminal to be connected to both LANs are high.
Even if the cost of modifying the terminal is acceptable, a problem which remains is the network architecture that will allow the terminal to distinguish between the backbone-connected LAN and the ad hoc LAN.
Furthermore, in a case where a plurality of ad hoc LANs exist and multicast communication is performed within each ad hoc LAN, a problem of the kind shown in FIG. 13 can arise. FIG. 13 illustrates an example of a case where wireless links are used as the means of transmission.
As shown in FIG. 13, wireless terminals 301xcx9c304 construct an ad hoc LAN referred to as xe2x80x9cad hoc LAN Axe2x80x9d, and wireless terminals 320xcx9c322 construct a different ad hoc LAN referred to as xe2x80x9cad hoc LAN Bxe2x80x9d. The areas capable of being reached by the radio waves from wireless terminals 301xcx9c304 and 320xcx9c322 are indicated by circles 310xcx9c313 and 330xcx9c332, respectively.
The wireless terminals 301xcx9c304 and 320xcx9c322 perform multicast communication within their own ad hoc LANs, respectively, using the packet shown in FIG. 14.
Since the areas within range of the radio waves from the terminals participating in multicasting within one of the ad hoc LANs and the areas within range of the radio waves from the terminals participating in multicasting within the other ad hoc LAN are not supposed to overlap each other, there is a possibility that both ad hoc LANs will be using identical multicast addresses.
Assume that the wireless terminal 303 connected to ad hoc LAN A attempts to participate in a multicast communication in progress among the wireless terminals 301, 302, 304 of ad hoc LAN B in a case where both ad hoc LANs are using the same multicast address. In such case the radio waves from wireless terminal 303 will reach the wireless terminal 321, which therefore will receive a different multicast communication but one having the same internet program (IP) multicast address. Thus, in cases where communication is carried out using the conventional packet format in an ad hoc LAN, duplication of multicast addresses is possible.
Accordingly, an object of the present invention is to provide an ad hoc network configuration, terminal and communication method or system through which it is possible to achieve connection and communication simultaneously between local area networks interconnected by a high-speed network (which local area networks are referred to as xe2x80x9cbackbone-connected LANsxe2x80x9d) and temporary LANs (referred to as xe2x80x9cad hoc LANsxe2x80x9d) not connected to a backbone network.
Further objects will become apparent in the entire disclosure.
According to a first aspect of the present invention, there is provided a method or system of setting up an ad hoc LAN wherein there simultaneously exist a plurality of backbone-connected LANs interconnected by a backbone network via routers and each having a plurality of terminals (referred to as xe2x80x9cterminal group 1xe2x80x9d) connected thereto, and a plurality of ad hoc LANs unconnected to the backbone network and each having a plurality of terminals (referred to as xe2x80x9cterminal group 2xe2x80x9d) connected thereto. A plurality of groups (referred to as xe2x80x9cmulticast groupsxe2x80x9d), in which all or part of the terminal groups 1 are members, are set up dynamically within a network constituted by the backbone network and backbone-connected LANs. Identifiers which identify respective ones of the multicast groups are defined for the multicast groups, communication between the members constituting the multicast groups is performed using the identifiers which identify the multicast groups. All or part of the terminal groups 2 are capable of communicating simultaneously not only with terminals connected to the ad hoc LANs to which the terminal groups 2 are connected but also with terminals connected to the backbone-connected LANs. In the method or system identifiers are decided which identify the multicast groups, for each of the ad hoc LANs, and identifying each of the ad hoc LANs using the identifiers.
According to a second aspect of the present invention, there is provided a terminal connectable to a backbone-connected LAN and to an ad hoc LAN simultaneously in an environment in which there simultaneously exist a plurality of backbone-connected LANs interconnected by a backbone network via routers and each having a plurality of terminals (referred to as xe2x80x9cterminal group 1xe2x80x9d) connected thereto, and a plurality of ad hoc LANs unconnected to the backbone network and each having a plurality of terminals (referred to as xe2x80x9cterminal group 2xe2x80x9d) connected thereto. A plurality of groups (referred to as xe2x80x9cmulticast groupsxe2x80x9d), in which all or part of the terminal groups 1 are members, are set up dynamically within a network constituted by the backbone network and the backbone-connected LANs. Identifiers which identify respective ones of the multicast groups are defined for the multicast groups; communication between the members constituting the multicast groups is performed using the identifiers which identify the multicast groups. All or part of the terminal groups 2 are capable of communicating simultaneously not only with terminals connected to the ad hoc LANs to which the terminal groups 2 are connected but also with terminals connected to the backbone-connected LANs. The terminal is capable of communicating simultaneously not only with terminals connected to the ad hoc LANs but also with terminals connected to the backbone-connected LAN; the terminal comprising: (a) a transceiver for ad hoc LAN purposes for sending signals to and receiving signals from transmission media constituting the ad hoc LANs; (b) a transceiver for backbone-connected LAN purposes for sending signals to and receiving signals from transmission media constituting the backbone-connected LANs; (c) a device driver for ad hoc LAN purposes corresponding to the transceiver for ad hoc LAN purposes; (d) a device driver for backbone-connected LAN purposes corresponding to the transceiver for backbone-connected LAN purposes; and (e) a device driver controller for sending signals to and receiving signals from both the device driver for ad hoc LAN purposes and the device driver for backbone-connected LAN purposes via a predetermined interface (referred to as xe2x80x9cinterface 1xe2x80x9d), and sending signals to and receiving signals from network layer software via the interface 1.
According to a third aspect of the present invention, there is provided a system or method of communication within an ad hoc LAN in an environment in which there simultaneously exist a plurality of backbone-connected LANs interconnected by a backbone network via routers and each having a plurality of terminals (referred to as xe2x80x9cterminal group 1xe2x80x9d) connected thereto, and a plurality of ad hoc LANs unconnected to the backbone network and each having a plurality of terminals (referred to as xe2x80x9cterminal group 2xe2x80x9d) connected thereto. A plurality of groups (referred to as xe2x80x9cmulticast groupsxe2x80x9d), in which all or part of the terminal groups 1 are members, are set up dynamically within a network constituted by the backbone network and the backbone-connected LANs; identifiers which identify respective ones of the multicast groups are defined for the multicast groups; communication between the members constituting the multicast groups is performed using the identifiers which identify the multicast groups; and it is so arranged that all or part of the terminal groups 2 are capable of communicating simultaneously not only with terminals connected to the ad hoc LANs to which the terminal groups 2 are connected but also with terminals connected to the backbone-connected LANs. The method comprising the steps of: (a) adding a network layer header, which is created based upon a destination address and an address of transmitting terminal, onto transmission data; and (b) communicating the transmission data, onto which the network layer header has been added, using a packet encapsulated by an encapsulation header created employing the identifier identifying an ad hoc LAN as a destination and employing the address of the transmitting terminal as the source of transmission.
According to a fourth aspect of the present invention, the identifiers for identifying the multicast groups set up in the ad hoc LANs are acquired through the following sequence: (a) a terminal A which starts the ad hoc LAN (referred to as xe2x80x9cad hoc LAN 1xe2x80x9d) transmits an identification test message and activates a timer, wherein the identifier test message includes an identifier (referred to as xe2x80x9cidentifier 1xe2x80x9d), for identifying a multicast group, desired to be used as the identifier of the ad hoc LAN 1, and has a predetermined address as the destination; (b) in a case where a terminal B that has received the identifier test message is already using the identifier 1, contained in the identifier test message, as the multicast group identifier within the backbone-connected LAN to which the terminal B is currently connected or as the identifier of another ad hoc LAN 2, the terminal B transmits an identifier refusal message, which includes the identifier 1, with the predetermined address as the destination; (c) in a case where the identifier refusal message is not received by the time the timer, which was activated by the terminal A that starts the ad hoc LAN 1, runs out of time, it is judged that the identifier 1 is not being used and this identifier is adopted as the identifier of the ad hoc LAN 1; (d) in a case where the identifier refusal message is received before the timer, which was activated by the terminal A that starts the ad hoc LAN 1, runs out of time, it is judged that the identifier 1 is currently in use; and (e) until an identifier judged ot to be in use is obtained, the terminal A that starts the ad hoc LAN 1 recursively transmits an identifier test message containing a different identifier and activates the timer.
According to a fifth aspect of the present invention, the device river controller of the terminal connected to the ad hoc LAN (a) manages an address list which includes other terminals connected to the ad hoc LAN to which the terminal is connected as well as identifiers of existing multicast groups, and (b) in a case where the terminal transmits data, delivers the transmission data to the device driver for ad hoc LAN purposes if a destination address exists in the address list and to the device driver for backbone-connected LAN purposes if the destination address does not exist in the address list.
According to a sixth aspect of the present invention, the address list of the device driver controller of the terminal connected to the ad hoc LAN is created as follows: (a) each terminal connected to the ad hoc LAN periodically transmits an address announcement message to a predetermined destination or destinations, wherein this address announcement message includes the address of the transmitting terminal and the identifier of the participating multicast group within the ad hoc LAN; and (b) the address announcement message is received by any of destinated terminals wherein the address list is created based upon the address of the transmitting terminal and the identifier of the participating multicast group within the ad hoc LAN, the address and the identifier being included in the address announcement message received by the destinated terminals.
According to a seventh aspect of the present invention, the device driver controller of the terminal connected to the ad hoc LAN (a) has the address list described above (refer to sixth aspect); (b) in a case where the terminal transmits data to a multicast group within the ad hoc LAN, the device driver controller creates the encapsulation header (refer to third aspect) by using an identifier which identifies the ad hoc LAN and the address of the terminal, to add the encapsulation header onto the transmission data, and delivers the transmission data to the device driver for ad hoc LAN purposes (refer to second aspect); and (c) upon receiving data from a multicast group within the an ad hoc LAN from the device driver for ad hoc LAN purposes, the device controller removes the encapsulation header from the received data and delivers the data to the network layer software of the terminal.
According to an eighth aspect, there is provided an ad hoc LAN in an environment in which there simultaneously exist a backbone-connected LAN connected by a backbone network via a router and having one or a plurality of terminals connected thereto, and an ad hoc LAN unconnected to said backbone network; wherein a terminal group constructs one or a plurality of multicast groups within a network constituted by the backbone network and the backbone-connected LAN. Identifiers which identify respective ones of the multicast groups are defined for said multicast groups. Communication between members of the terminal group constituting the multicast groups is performed using the identifiers which identify the multicast groups. And the ad hoc LAN is set up as a multicast group and a multicast address is appropriately assigned thereto, enabling to distinguish said ad hoc LAN from other multicast groups which exist within said backbone-connected LAN and backbone network.
According to a ninth aspect, there is provided a terminal connectable to both an ad hoc LAN and a backbone-connected LAN simultaneously, comprising: (a) a device driver and a transceiver implementing a data link layer and a physical layer decided in each LAN in order to make a connection to both said ad hoc LAN and said backbone-connected LAN; and (b) a device driver controller between a network layer and said device driver.
The device driver controller has an address list of other terminals connected within the ad hoc LAN to which its own terminal is connected; wherein:
(1) in a case where data is transmitted from its own terminal, said device driver controller accepts transmission data, from a higher layer, supplied by said network layer upon having a destination address added thereto, refers to said address list, determines whether the destination address is a terminal in an ad hoc LAN or in a backbone-connected LAN, selects a suitable device driver and transceiver and outputs the transmission data;
(2) in a case where its own terminal transmits data to a multicast group within an ad hoc LAN, said device driver controller creates an encapsulation header using an identifier which identifies said ad hoc LAN and an address of its own terminal, adds said encapsulation header onto the transmission data and supplies the transmission data to the device driver for the ad hoc LAN; and
(3) when data from a multicast group within said ad hoc LAN is received from the device driver for the ad hoc LAN, said device driver controller removes the encapsulation header from the received data and delivers the received data to said network layer.
Thus, in accordance with the present invention, as described above, it is possible to make a connection to both an ad hoc LAN and a backbone-connected LAN simultaneously so that both LANs can communicate with each other. This is achieved by making it possible to distinguish between an ad hoc LAN and a backbone-connected LAN and arranging it so that duplication of multicast group addresses will not occur.
Other features and advantages of the present invention will be apparent from the following description taken in conjunction with the accompanying drawings, in which like reference characters designate the same or similar parts throughout the figures thereof.